package Draft;

public class Inversion_count {

    public class Inversion_Count {
        int[] tmp, nums;

        public int reversePairs(int[] _nums) {
            nums = _nums;
            int n = nums.length;
            tmp = new int[n];
            return mergeSort(0, n - 1);
        }

        // mergeSort 的任务是找出传入区间有多少个逆序对，并且顺手排序
        public int mergeSort(int left, int right) {

            // 只有一个元素，或者没有元素，这种情况不可能有逆序对
            if (left >= right) {
                return 0;
            }

            int ret = 0;
            // 1. 选择一个中间点，把数组划分成两个部分
            int mid = (left + right) / 2;
            // [left , mid] [mid+1 , right]

            // 2. 左半部分的个数 + 排序 +右边部分的个数 + 排序
            ret += mergeSort(left, mid);
            ret += mergeSort(mid + 1, right);

            // 3. 一左一右逆序对的个数
            int cur1 = left, cur2 = mid + 1, i = 0;
            while (cur1 <= mid && cur2 <= right) {
                // 升序
                if (nums[cur1] <= nums[cur2]) {
                    tmp[i++] = nums[cur1++];
                } else {
                    ret += mid - cur1 + 1;
                    tmp[i++] = nums[cur2++];
                }
            }

            // 4. 处理没有移动完的指针
            while (cur1 <= mid) tmp[i++] = nums[cur1++];
            while (cur2 <= right) tmp[i++] = nums[cur2++];

            // 5. 还原
            for (int j = left; j <= right; j++)
                nums[j] = tmp[j - left];

            return ret;
        }

        public int mergeSort1(int left, int right) {

            // 只有一个元素，或者没有元素，这种情况不可能有逆序对
            if (left >= right) {
                return 0;
            }

            int ret = 0;
            // 1. 选择一个中间点，把数组划分成两个部分
            int mid = (left + right) / 2;
            // [left , mid] [mid+1 , right]

            // 2. 左半部分的个数 + 排序 +右边部分的个数 + 排序
            ret += mergeSort(left, mid);
            ret += mergeSort(mid + 1, right);

            // 3. 一左一右逆序对的个数
            int cur1 = left, cur2 = mid + 1, i = 0;
            while (cur1 <= mid && cur2 <= right) {
                // 降序
                if (nums[cur1] <= nums[cur2]) {
                    tmp[i++] = nums[cur2++];
                } else {
                    ret += right - cur2 + 1;
                    tmp[i++] = nums[cur1++];
                }
            }

            // 4. 处理没有移动完的指针
            while (cur1 <= mid) tmp[i++] = nums[cur1++];
            while (cur2 <= right) tmp[i++] = nums[cur2++];

            // 5. 还原
            for (int j = left; j <= right; j++)
                nums[j] = tmp[j - left];

            return ret;
        }
}
